home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_13_08 / gottner / hashmap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-07-10  |  2.8 KB  |  108 lines
  1. /*--------------------------------------------------------------*
  2.  *      class Map<>
  3.  *
  4.  * The map class maps keys to values.
  5.  * (an associative array class)
  6.  *--------------------------------------------------------------*/
  7.  
  8. #include <stddef.h>
  9. #define HASHSIZE 31
  10.  
  11. struct VPAssoc {
  12.     VPAssoc *next;   // next key/value pair in bucket
  13.     void *   key;    // pointer to the key
  14.     void *   value;  // pointer to the value
  15. };
  16.  
  17.  
  18. class VPmap {
  19. protected:
  20.     typedef int (*KeyCompareEqProc)(
  21.                         const void *a,
  22.                         const void *b);
  23.  
  24.     typedef unsigned (*KeyHashProc)(
  25.                         const void *key);
  26.  
  27.     typedef void (*KeyValCreateProc)(
  28.                         const VPmap *dict,
  29.                         const void * currentKey,
  30.                         void *&      keyCopy,
  31.                         void *&      newValue);
  32.  
  33.     typedef void (*KeyValDestroyProc)(
  34.                         void *key,
  35.                         void *value);
  36.  
  37.     KeyCompareEqProc  isEqual;
  38.     KeyHashProc       hash;
  39.     KeyValCreateProc  CreateKeyAndValue;
  40.     KeyValDestroyProc DestroyKeyAndValue;
  41.     VPAssoc **        keys;
  42.     size_t            hashsize;
  43.  
  44.     /// constructor
  45.     VPmap(size_t,
  46.           KeyHashProc,
  47.           KeyCompareEqProc,
  48.           KeyValCreateProc,
  49.           KeyValDestroyProc);
  50.  
  51.     ~VPmap();
  52.  
  53. private:
  54.     VPmap(const VPmap &); // copy and assignment illegal
  55.     VPmap &operator= (const VPmap &);
  56.  
  57. protected:
  58.     void *index(const void *);
  59.  
  60.     /// apply a function to each key and value
  61.     typedef void (*VPiterProc)(const void *, void *, void *);
  62.     void apply(VPiterProc, void *);
  63. };
  64.  
  65.  
  66. /*---------------------------------------------------------*
  67.  * Templates
  68.  *---------------------------------------------------------*/
  69.  
  70. template <class KEY, class VAL>
  71. struct Map : private VPmap {
  72.     typedef unsigned (*KeyHashFunction)(const KEY &);
  73.     Map(KeyHashFunction,
  74.         const VAL & = VAL(),
  75.         size_t = HASHSIZE);
  76.  
  77.     VAL &operator[](const KEY &key)
  78.         {
  79.         return * (VAL *) index(&key);
  80.         }
  81.  
  82.     typedef void (*IterProc)(const KEY &, VAL &, void *);
  83.     void apply(IterProc proc, void *data)
  84.         {
  85.         VPmap::apply(VPiterProc(proc), data);
  86.         }
  87.  
  88. private:
  89.     VAL default_value;
  90.  
  91.     static void CreateKeyVal(
  92.                         const Map<KEY, VAL> &,
  93.                         const KEY &,
  94.                         KEY *&,
  95.                         VAL *&);
  96.  
  97.     static void DestroyKeyVal(KEY *key, VAL *value);
  98.     static int  CmpKeys(const KEY &a, const KEY &b);
  99. };
  100.  
  101.   /* some compilers instantiate templates in header files */
  102. #if defined __BCPLUSPLUS__ || defined __GNUC__
  103. #include "hashmap.cc"
  104. #endif
  105.  
  106.  
  107.  
  108.